package midalgorithms.treeandmap;

import java.util.ArrayList;
import java.util.List;

public class _01InorderTraversal {
    public static List<Integer> inorderTraversal(TreeNode root) {
        /** 栈实现二叉树的中序遍历
         *  迭代法，比较难以理解
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }
        */
        List<Integer> res = new ArrayList<>();
        midTraversal(res,root);
        return res;
    }

    private static void midTraversal(List<Integer> list,TreeNode root) {
        if (root == null){
            return;
        }
        if (root.left != null){
            midTraversal(list,root.left);
        }
        list.add(root.val);
        if (root.right != null){
            midTraversal(list,root.right);
        }
    }
}
